DROPS

Document

DOI: 10.4230/LIPIcs.ICALP.2018.92

Fully Dynamic MIS in Uniformly Sparse Graphs

Authors: Krzysztof Onak, Baruch Schieber, Shay Solomon, and Nicole Wein

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

We consider the problem of maintaining a maximal independent set (MIS) in a dynamic graph subject to edge insertions and deletions. Recently, Assadi, Onak, Schieber and Solomon (STOC 2018) showed that an MIS can be maintained in sublinear (in the dynamically changing number of edges) amortized update time. In this paper we significantly improve the update time for uniformly sparse graphs. Specifically, for graphs with arboricity alpha, the amortized update time of our algorithm is O(alpha^2 * log^2 n), where n is the number of vertices. For low arboricity graphs, which include, for example, minor-free graphs as well as some classes of "real world" graphs, our update time is polylogarithmic. Our update time improves the result of Assadi et al. for all graphs with arboricity bounded by m^{3/8 - epsilon}, for any constant epsilon > 0. This covers much of the range of possible values for arboricity, as the arboricity of a general graph cannot exceed m^{1/2}.

Cite as

Krzysztof Onak, Baruch Schieber, Shay Solomon, and Nicole Wein. Fully Dynamic MIS in Uniformly Sparse Graphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 92:1-92:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{onak_et_al:LIPIcs.ICALP.2018.92,
  author =	{Onak, Krzysztof and Schieber, Baruch and Solomon, Shay and Wein, Nicole},
  title =	{{Fully Dynamic MIS in Uniformly Sparse Graphs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{92:1--92:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.92},
  URN =		{urn:nbn:de:0030-drops-90968},
  doi =		{10.4230/LIPIcs.ICALP.2018.92},
  annote =	{Keywords: dynamic graph algorithms, independent set, sparse graphs, graph arboricity}
}

Search Results

Documents authored by Onak, Krzysztof

Fully Dynamic MIS in Uniformly Sparse Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message